package bloomfilterdemo;

import java.util.BitSet;

/**
 * Creat with IntelliJ IDEA
 * Description:
 * User:WZW
 * Date:2022-10-17
 * Time:21:29
 */

 class SimpleHash {
     public int cap;
     public int seed;

    public SimpleHash(int cap, int seed) {
        this.cap = cap;
        this.seed = seed;
    }

    int hash(String key) {
        int h;
        return (key == null) ? 0 : (seed * (cap - 1)) & ((h = key.hashCode()) ^ (h >>> 16));
    }
}

public class MyBloomFilter {

     public static final int DEFAULT_SIZE = 1 << 20;
     public BitSet bitSet;
     public int usedSize;
     public static final int[] seeds = {5,7,11,13,27,33};
     public SimpleHash[] simpleHashes;
     public MyBloomFilter() {
        bitSet = new BitSet(DEFAULT_SIZE);
        simpleHashes = new SimpleHash[seeds.length];
         for (int i = 0; i < simpleHashes.length; i++) {
             simpleHashes[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
         }
     }

    /**
     * 添加元素到布隆过滤器
     * @param val
     */
     public void add(String val) {
         for (SimpleHash simpleHash : simpleHashes) {
             int index = simpleHash.hash(val);
             bitSet.set(index);
         }
     }

    /**
     * 是否包含 val，这里会存在一定的误判的
     * @param val
     * @return
     */
     public boolean contains(String val) {
         for (SimpleHash simpleHash : simpleHashes) {
             int index = simpleHash.hash(val);
             boolean flg = bitSet.get(index);
             if (!flg) {
                 return false;
             }
         }
         return true;
     }

    public static void main(String[] args) {
        MyBloomFilter myBloomFilter = new MyBloomFilter();
        myBloomFilter.add("hello");
        myBloomFilter.add("hello2");
        myBloomFilter.add("bit");
        myBloomFilter.add("haha");

        System.out.println(myBloomFilter.contains("hello"));
        System.out.println(myBloomFilter.contains("hello3"));
        System.out.println(myBloomFilter.contains("he"));
    }
}
